package practice1_100;


import java.util.HashMap;
import java.util.concurrent.atomic.AtomicInteger;

public class Practice279 {
    public int numSquares(int n) {
        int[] res=new int[n+1];
        for(int i=1;i*i<=n;i++){
            res[i*i]=1;
        }
        for(int i=1;i<res.length;i++){
            for(int j=1;j<i;j++){
                if(res[i]!=0) res[i]=Math.min(res[i],res[j]+res[i-j]);
                else res[i]=res[j]+res[i-j];
            }
        }
        return res[n];
    }

    public static void main(String[] args) {
        int a=new Practice279().numSquares(81);
        System.out.println(a);
        HashMap hashMap=null;
        AtomicInteger i=new AtomicInteger(10);
//        jkvhsvjk
    }
}
